| layout | title | description | date | categories | comments |
|---|---|---|---|---|---|
post |
Insertion Sort |
Insertion Sort |
2019-04-29 13:05:00 -0700 |
Algorithm |
true |
삽입 정렬은 리스트의 길이를 하나씩 늘리면서 맨 끝의 원소가 제 자리를 찾을 수 있게 비교하여 정렬하는 알고리즘이다.
- 삽입 정렬의 특징
- O(N^2)
- 이미 정렬되어 있는 리스트의 경우, 원소의 위치를 바꾸지 않아도 되므로 O(N)
- 리스트의 길이가 2일 때부터 한 번의 과정을 통해 하나의 원소의 위치를 결정함으로써 원소들의 위치를 순서대로 정해주므로 매 과정마다 리스트의 정렬에 대한 정확도를 보장한다.